---- Vacío. ----
------------------------------------------------------------------------
---- Crea un diccionario vacío con la función   ---- 
---- de comparación pasada como parámetro.      ----

vacío :: Comp clave -> Diccionario clave valor
vacío clave = Dicc clave Nothing


------------------------------------------------------------------------
---- Definir. ----
------------------------------------------------------------------------
---- Dada una clave, un valor y un diccionario, define una  ----
---- clave con su valor correspondiente en el diccionario.  ----

definir :: clave -> valor -> Diccionario clave valor -> Diccionario clave valor
definir clave valor (Dicc a b) = 
        Dicc a (Just (insertar clave valor a a23) )
        where a23 = case b of 
                    Nothing -> Hoja (clave, valor)
                    Just b  -> b
                                                                

------------------------------------------------------------------------

---- Obtener. ----
------------------------------------------------------------------------
---- Dada una clave y un diccionario, devuelve su valor ----
---- si está en el diccionario, y Nothing si no está.   ----


-- Se recorre hasta la hoja correspondiente utilizando las reglas del invariante
-- del arbol 2-3. Se asume que se tiene un arbol 2-3 bien balanceado. Entonces
-- la complejidad sera de O(log n)

obtener :: Eq clave => clave -> Diccionario clave valor -> Maybe valor
obtener clave (Dicc a b) = case b of
                           Nothing -> Nothing
                           Just b -> if esHoja b then checkClave clave b 
                                                 else obtener clave (recorrerArbol clave a b)

checkClave clave (Hoja (ch,vh)) = if clave == ch then Just vh else Nothing

recorrerArbol clave cmp arbol = case arbol of
        Dos x a1 a2 -> if clave `cmp` x then (Dicc cmp (Just a1))
                                   else (Dicc cmp (Just a2))
        Tres x y a1 a2 a3 -> if clave `cmp` x then (Dicc cmp (Just a1))
                             else 
                            (if clave `cmp` y then (Dicc cmp (Just a2))
                             else (Dicc cmp (Just a3)))


--Ejercicio 9
claves::Diccionario clave valor -> [clave]

